import java.util.Random;

/**
 * @author: gao
 * @create-date: 2025/3/9 0:01
 */

public class Sort {
    public void DisOrder(int[] array){
        Random ran = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = ran.nextInt(1,40);
        }
    }

    public void QuickSort(int[] array){
        Quick(array,0,array.length-1);
    }

    public void Quick(int[] array,int start,int end){
        if(start >= end){//如果结点的右子树为空，就不用遍历右边
            return;
        }
        int par = partition(array,start,end);
        Quick(array,start,par-1);
        Quick(array,par+1,end);
        //当start==end时，递归条件结束
    }

    private int partition(int[] array, int left, int right) {
        int i = left;
        int tmp = array[left];
        while(left < right){
            while(left < right && array[right] >= tmp){
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

}